// 实现 strStr() 函数。

// 给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。
// 如果不存在，则返回  -1 。当 needle 是空字符串时我们应当返回 0 


// 暴力法1
// 执行用时：1628 ms, 在所有 C 提交中击败了7.47% 的用户
int strStr(char * haystack, char * needle){
    int len1= strlen(haystack), len2 = strlen(needle);
    if (len2 == 0) return 0;
    
    int cnt;
    for (int i = 0; i < len1; i++) {
        cnt = 0;
        for (int j = 0; j < len2; j++) {
            if (haystack[i + cnt] == needle[j]) cnt++;
            else break;
        }
        if (cnt == len2) return i;
    }
    return -1;
}

// 暴力法优化
// 执行用时：4 ms, 在所有 C 提交中击败了75.47% 的用户
// 内存消耗：5.7 MB, 在所有 C 提交中击败了89.91% 的用户
int strStr(char * haystack, char * needle){
    int len1= strlen(haystack), len2 = strlen(needle);
    if (len2 == 0) return 0;

    int cnt = 0;
    for (int i = 0; i < len1; i++) {
        if (haystack[i] == needle[0] && len1 - i >= len2) {
            for (int j = 0; j < len2; j++) {
                if (haystack[i + cnt] == needle[j]) cnt++;
                else break;
            }
            if (cnt == len2) return i;
            else cnt = 0;
        }
    }
    return -1;
}